The present invention relates generally to signal processing and, more particularly, to a method and an apparatus for data compression based on vector quantization and their application to image coding.
The goal of vector quantization is to reduce the amount of data required to represent an original data set. By those skilled in the art, this data reduction is referred to as data compression or data coding. Data compression reduces transmission data rate and memory storage requirements. In limited bandwidth telecommunications applications, data compression not only eases overall system requirements but also, can be essential for enabling communication of certain kinds of information. For example, transmission of video information over digital communication networks would require bit rates which exceed the capacity of many systems. Thus, effective data compression methods render viable many previously impossible system implementations.
Vector quantization is only one of myriad data compression techniques and has the comparative potential advantage of a greater compression ratio for a given signal integrity loss. Whereas scalar quantization refers to mapping individual samples of a signal, vector quantization groups a plurality of signal sample values, forming a vector. The mapping of this vector into a code possessing fewer bits than the vector is referred to as vector quantization. This mapping is accomplished by comparing the vector with a code book composed of code words which are a representative subset of the set of possible vectors and are each addressed by a code. The code corresponding to the code word which best describes the vector is then used to represent the original signal group. This code is transmitted or stored and recovery of the signal group is accomplished by using the code to access an identical code book. Vector quantization is well suited for compression of video or audio signals since successive signal samples are correlated.
In the application of vector quantization to image data, the digitized values corresponding to an n by m block of pixels is treated as a single vector, where n and m are integers. If each pixel were represented by 8 bits, then 8nm bits would be required to convey the image block information at a data rate corresponding to 8FLP, where F is the frame rate, L is the number of lines per frame, and P is the number of pixels per line. For a typical video signal this data rate would exceed the capacity of established data channels. Conventional vector quantization reduces the data rate by comparing each 8nm bit length vector to a code book containing N representative 8nm-dimensional code word vectors and choosing the most similar vector. The code word index, which has dimension k=log.sub.2 N, results, is used as the data representing an original 8nm-dimensional vector and thus a compression ratio of r=8nm/k results. The essence of the compression is that the 2.sup.8nm possible combinations for the image block vector can be represented by a reduced set of 2.sup.k vectors, requiring k bits to represent a block instead of 8nm bits.
FIG. 1 illustrates the foregoing vector quantization description for a 2.times.2 pixel block with eight bits per pixel, yielding a 32 bit input vector. The vector code table contains N representative 32 bit vectors which are compared to the input vector according to some distortion measure, and the k bit address (index) to the minimum distortion vector is output by the quantization process. The output vector index could be 16 bits, for example, corresponding to N=64K vector code words in the vector code table, and to a compression ratio of 2:1.
For a given compression ratio r, the code book memory requirements and concomitantly the code book searching computational requirements increases approximately as the product of the input vector bit length and the number of vector codes (eg. (8nm)2.sup.8nm/r) and thus, the block size, n by m, is generally kept small. Small block sizes, however, result in "blocky" reconstructed images due to edge discontinuities and gray-level discontinuities between adjacent blocks.
Attempts to mitigate the effects of a small block have included using separate codebooks for edge and texture information, statistical correlation among blocks, and orthogonal transformations prior to vector quantization. For example, in U.S. Pat. No. 4,829,376, issued May 9, 1989, Hammer teaches a vector quantization method using an orthonormal transformation with a Hadamard matrix which reduces the "blockiness" and also reduces vector code table searching computational requirements by eliminating multiplication in the search criterion. In addition, improved methods for organizing and searching the codebook have reduced the computational requirements involved in vector quantization such as the method taught by Aldersberg in U.S. Pat. No. 4,907,276, issued Mar. 6, 1990.
Although many approaches have been previously made to vector quantization of image data, this field is still in its infancy and further improvements are required for commercial implementation.
Accordingly, an object of the present invention is to provide a method and system for image coding based on vector quantization which increases the compression ratio.
A specific advantage is that the increased compression ratio allows larger blocks to be encoded for a given code dimension, thereby improving reconstructed image quality.
A further advantage of the present invention is that the increased compression ratio renders digital video transmission practical over diverse transmission media, enabling myriad digital video based systems.
A related advantage is that since the increased compression ratio may result in video output data which does not occupy the full, allotted digital transmission bandwidth, "opportunistic," data may be interjected into the digital video transmission.
The foregoing specific objects and advantages of the invention are illustrative of those which can be achieved by the present invention and are not intended to be exhaustive or limiting of the possible advantages which can be realized. Thus, these and other objects and advantages of the invention will be apparent from the description herein or can be learned from practicing the invention, both as embodied herein or as modified in view of any variations which may be apparent to those skilled in the art.